Most instructions in a computer instruction set operate on several source operands to generate results. The instructions name, either explicitly or through an indirection, the source and destination locations where values are read from or written to. A name may be either a logical, or an architectural, register or a location in memory.
Instructions involving register operands are faster than those involving memory operands. For some microprocessor architectures, instructions naming memory operands are translated, or decoded, into microinstructions that transfer operand values from memory to logical registers and then perform the decoded computations. The number of logical registers often is limited, compilers efficiently should utilize logical registers to generate efficient code.
The number of physical registers available in a microprocessor typically exceeds the number of logical, or architectural, registers, so that register renaming may be utilized to increase performance. More than one physical register may be renamed to a logical register. Each physical register may correlate to a non-retired instruction, and, therefore, a plurality of non-retired instructions should utilize a plurality of physical registers. In particular, for out-of-order processors, register renaming allows instructions to be executed out of their original program order. Thus, for many out-of-order processors, an instruction is renamed so that logical registers named in the original instruction are renamed to physical registers.
Renaming a logical register involves mapping a logical register to a physical register. These mappings are stored in a Register Alias Table (“RAT”). A RAT maintains the latest mapping for each logical register. A RAT is indexed by logical registers, and provides mappings to corresponding physical registers. This activity may be called dependency tracking.
FIG. 1 depicts a register renaming and dependency tracking scheme involving three structures: a RAT 110, a active list 102, and a free list 104. For each logical register specified by a renamed instruction, an unused physical register from the free list 104 is allocated. RAT 110 is updated with this new allocation. Physical registers are free to be used again, or reclaimed, once they cannot be referenced by instructions in the current instruction window.
Based upon the data structures depicted in FIG. 1, one method for register reclaiming is to reclaim a physical register when the instruction that evicted it from RAT 110 retires. Thus, the instruction that created the new allocation to the physical register is retired for reclaiming to occur. As a result, whenever a new allocation updates RAT 110, the evicted old allocation is pushed into active list 102. An active list 102 entry is associated with each instruction in the instruction window. When an instruction retires, the physical register evicted from RAT 110 and recorded in active list 102, if any, is reclaimed and pushed into free list 104. The cycle is depicted in FIG. 1.
During register renaming, free list 104 allocates an unused physical register when an instruction specifies a logical, or architectural, register as a destination. The instruction source physical registers are read from RAT 110 based on the instruction source logical registers. Afterwards, RAT 110 maps the destination logical register to the newly allocated physical register from free list 104. When a destination logical register is renamed, subsequent instructions cannot read the physical register that previously was mapped to that logical register. As discussed above, an appropriate condition for register reclaiming is to reclaim a physical register when the instruction that generated the new mapping in RAT 110 retires. Further, the old mapping is pushed into active list 102 from RAT 110. When the corresponding instruction retires, the old mapping is reclaimed and pushed into free list 104.
FIG. 2 depicts an example of a recovery scheme for the register renaming structure. The renaming structures described in FIG. 1 are repaired when an exception occurs in the processor. Recovery techniques seek to restore the correct state to RAT 110, active list 102 and free list 104. Several events may terminate a normal instruction flow. Common reasons for exceptions include mispredicted branches, interupts, or exceptions. When these events occur, instruction window buffer 112 should be flushed after the point of the exception. In addition, all three structures involved in register renaming should be repaired to reflect the new logical, or architectural state.
FIG. 2a depicts the original state of the processor. Instruction window 110 holds four instructions that have not been renamed. Instructions 1, 3 and 4 specify logical register EAX as their destinations. Active list 102 is empty. The current mapping of logical register EAX is physical register R1. Free list 104 contains unallocated registers R2 to R5.
FIG. 2b depicts that state of the renaming structures after all four instructions are renamed. Each allocation of a new physical register for EAX pushed the previous mapping into active list 102. The current mapping of EAX in RAT 110 is physical register R4. Physical registers R1, R2 and R3 correlate to old mappings evicted from RAT 110. Free list 104 contains unallocated physical register R5.
If the branch instruction of instruction 2 in instruction window buffer 112 is mispredicted, then all three remaining structures need to be repaired so they reflect the state of the machine right L5 after instruction 2. One method to recover RAT 110 is to establish checkpoints of its content for every dispatched branch. RAT 110 can be recovered by copying the content of the corresponding checkpoint into RAT 110. Active list 102 may be repaired by flushing all entries past the mispredicted branch, or instructions 3 and 4 in the example. FIG. 2c depicts a complex algorithm to recover free list 104. Part of the physical registers in RAT 110 and active list 102 are returned to free list 104. Algorithms may need to be implemented to recover the physical registers to free list 104. Merely recovering flushed entries may lead to physical registers being recovered incorrectly. Thus, a need has arisen for a method for recovering free list 104 in a more efficient manner.